#include "UnorderedSet.h"

int main()
{
    lwj::unordered_set<int> se;
    for(int i = 0; i < 10; i++) se.insert(i);
    se.insert(99);
    cout << se.erase(99).second << endl;
    return 0;
}


#ifndef HASHTABLE_HASHTABLE_H
#define HASHTABLE_HASHTABLE_H
#include <vector>
#include <list>
#include <iostream>
using namespace std;

namespace lwj
{
    template<class T>
    struct HTNode
    {
        T _date;
        HTNode* _next;

        HTNode(const T& date = T())
            : _date(date),
              _next(nullptr)
        {}
    };



    template<class K, class T, class KeyOfT, class hash>
    class HashTable;

    template<class K, class T, class Ptr, class Ref, class KeyOfT, class hash>
    struct HashIterator
    {
        HTNode<T>* _node;
        const vector<HTNode<T>*>* _ht;
        HashIterator(const HTNode<T>* node, const vector<HTNode<T>*>* ht)
            :_node(node),
              _ht(ht)
        {}

        HashIterator& operator++()
        {
            if(_node->_next) _node = _node->_next;
            else
            {
                hash hs;
                KeyOfT kot;
                size_t sz = _ht->size();
                size_t hashi = hs(kot(_node->_date)) % sz;
                while(++hashi != sz) if(_ht[hashi]) _node = _ht[hashi];
                if(hashi == sz) _node = nullptr;
            }
            return _node;
        }

        HashIterator operator++(int)
        {
            HTNode<T> node = _node;
            if(_node->_next) _node = _node->_next;
            else
            {
                hash hs;
                KeyOfT kot;
                size_t sz = _ht->size();
                size_t hashi = hs(kot(_node->_date)) % sz;
                while(++hashi != sz) if(_ht[hashi]) _node = _ht[hashi];
                if(hashi == sz) _node = nullptr;
            }
            return node;
        }

        HashIterator& operator--()
        {
            hash hs;
            KeyOfT kot;
            size_t sz = _ht->size();
            size_t hashi = hs(kot(_node->_date)) % sz;
            HTNode<T>* cur;
            if(_ht[hashi] == _node)
            {
                while(--hashi >= 0)
                {
                    if(_ht[hashi])
                    {
                        cur = _ht[hashi];
                        while (cur->_next) cur = cur->_next;
                        _node = cur;
                    }
                }
                if(hashi < 0) _node = nullptr;
            }
            else
            {
                cur = _ht[hashi];
                while(cur->_next != _node) cur = cur->_next;
                _node = cur;
            }
            return _node;
        }

        HashIterator operator--(int)
        {
            HTNode<T> node = _node;
            hash hs;
            KeyOfT kot;
            size_t sz = _ht->size();
            size_t hashi = hs(kot(_node->_date)) % sz;
            HTNode<T>* cur;
            if(_ht[hashi] == _node)
            {
                while(--hashi >= 0)
                {
                    if(_ht[hashi])
                    {
                        cur = _ht[hashi];
                        while (cur->_next) cur = cur->_next;
                        _node = cur;
                    }
                }
                if(hashi < 0) _node = nullptr;
            }
            else
            {
                cur = _ht[hashi];
                while(cur->_next != _node) cur = cur->_next;
                _node = cur;
            }
            return node;
        }

        Ref operator*() {return _node->_date;}
        Ptr operator->() {return &_node->_date;}

        bool operator==(const HashIterator& it) {return _node == it._node;}
        bool operator!=(const HashIterator& it) {return !operator==(it);}
    };

    template<class K, class T, class KeyOfT, class hash>
    class HashTable
    {
    public:
        template<class K, class T, class Ptr, class Ref, class KeyOfT, class hash>
        friend struct HashIterator;
        typedef HashIterator<K, T, T*, T&, KeyOfT, hash> iterator;
        typedef HashIterator<K, T, const T*, const T&, KeyOfT, hash> const_iterator;

        iterator begin()
        {
            int i = -1;
            while(++i != _ht.size())
            {
                if(_ht[i]) return iterator(_ht[i], _ht);
            }
        }

        const_iterator end() const {return {nullptr, _ht};}

        const_iterator begin() const
        {
            int i = -1;
            while(++i != _ht.size())
            {
                if(_ht[i]) return iterator(_ht[i], _ht);
            }
        }

        iterator end() {return {nullptr, _ht};}

        HashTable()
        {
            _ht.resize(10, nullptr);
            _sz = 0;
        }

        ~HashTable()
        {
            HTNode<T>* cur, *next;
            for(auto e : _ht)
            {
                cur = e;
                while (cur)
                {
                    next = cur->_next;
                    delete cur;
                    cur = next;
                }
            }
            _sz = 0;
        }

        pair<iterator, bool> insert(const T& date)
        {
            KeyOfT kot;
            iterator it = find(kot(date)).first;
            if(it != end()) return {iterator(nullptr, _ht), false};
            hash func;
            size_t sz = _ht.size();
            if(_sz == sz)
            {
                vector<HTNode<T>*> ht(_sz * 2);
                HTNode<T>* cur, *next, *tmp;
                for(auto e : _ht)
                {
                    cur = _ht;
                    while (cur)
                    {
                        next = cur->_next;
                        size_t hashi = func(kot(cur->_date)) % (_sz * 2);
                        if(_ht[hashi] == nullptr) _ht[hashi] = cur;
                        else
                        {
                            tmp = _ht[hashi];
                            _ht[hashi] = cur;
                            cur->_next = tmp;
                        }
                        cur = next;
                    }
                }
                swap(_ht, ht);
            }
            size_t hashi = func(kot(date)) % (sz);
            HTNode<T>* newNode = new HTNode<T>(date);
            HTNode<T>* tmp;
            if(_ht[hashi] == nullptr) _ht[hashi] = newNode;
            else
            {
                tmp = _ht[hashi];
                _ht[hashi] = newNode;
                newNode->_next = tmp;
            }
            return {iterator(newNode, _ht), true};
        }

        pair<iterator, bool> find(const K& key)
        {
            size_t hashi = func(key) % (_ht.size());
            HTNode<T>* cur = _ht[hashi];
            while (cur)
            {
                if(kot(cur->_date) == key) return {iterator(cur, _ht), true};
                cur = cur->_next;
            }
            return {nullptr, false};
        }

        pair<iterator, bool> erase(const K& key)
        {
            size_t hashi = func(key) % (_ht.size());
            HTNode<T>* cur = _ht[hashi];
            HTNode<T>* prev;
            while (cur)
            {
                if(kot(cur->_date) == key)
                {
                    if(prev)
                    {
                        prev->_next = cur->_next;
                    }
                    else _ht[hashi] = cur->_next;
                    delete cur;
                    return {iterator(prev->_next, _ht), true};
                }
                prev = cur;
                cur = cur->_next;
            }
            return {itertor(nullptr, _ht), false};
        }
    private:
        vector<HTNode<T>*> _ht;
        size_t _sz;
    };
}

#endif//HASHTABLE_HASHTABLE_H




